;; e1.17

#|
perform multiplication using only arithmetic in addition to a double and halve operator
the requirement is to develop this multiplication procedure to exhibit logarithmic time and space requirement growth
|#

(define (mult a b)
    (define (halve   x) (/ x 2))
    (define (double  x) (* x 2))
    (define (is-even x) (= (remainder x 2) 0))
    (cond ((= b 1)
            a)
          ((is-even b)
            (mult (double a) (halve b)))
          (else
            (+ a (mult a (- b 1))))))

(mult 2 2)
(* 2 2)
(mult 2 3)
(* 2 3)
(mult 5 10)
(* 5 10)
(mult 5 19)
(* 5 19)
(mult 7 9)
(* 7 9)
(mult 7 2)
(* 7 2)

; try to provide evidence for logarithmic growth
(display "evidence for logarithmic growth\n(mult 20 40)\n")
(mult 20 40)
(mult 40 20)
(mult 80 10)
(mult 160 5)
(+ 160 (mult 160 4))
(+ 160 (mult 320 2))
(+ 160 (mult 640 1))
(display "takes 6 steps\n(mult 20 (* 40 2))\n")
(mult 20 (* 2 40))
(mult 40 40)
(mult 80 20)
(mult 160 10)
(mult 320 5)
(+ 320 (mult 320 4))
(+ 320 (mult 640 2))
(+ 320 (mult 1280 1))
(display "takes 6+1 steps for double the n
theta(n) = theta(n/2)+1, therefore time requirement is theta(log(n))
space requirement should be likewise..\n")
